package 剑指offer;

import java.util.HashMap;
import java.util.Hashtable;
import java.util.LinkedHashMap;
import java.util.Map;

public class 剑指Offer48最长不重复字串 {
    public static void main(String[] args) {
        Hashtable<Integer,Character> hash = new Hashtable();
        System.out.println(lengthOfLongestSubstring("aaa"));
    }

    //使用table在使用双指针
    public static int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        int max = 1;
        if(s.length() == 0) return 0;
        if(s.length() == 1) return 1;


        Hashtable<Integer,Character> hash = new Hashtable<Integer,Character>();

        char[] ch = s.toCharArray();

        hash.put(right,ch[right]);

        for(int i = 1;i < ch.length;i++){
            if(hash.containsValue(ch[i])){
                max = max >= i - left ? max : i - left;
                while(hash.get(left).equals(ch[i]) == false){
                    hash.remove(left);
                    left++;
                }
                hash.remove(left);
                left++;

                hash.put(i,ch[i]);
            }else{
                hash.put(i,ch[i]);
                max = max >= hash.size() ? max : hash.size();
            }
        }

        return max;
    }


    //使用hashMap会报同步修改异常
    public static int lengthOfLongestSubstring1(String s) {
        if("".equals(s)) return 0;
        char[] ch = s.toCharArray();
        HashMap<Character,Boolean> map = new LinkedHashMap<>();
        int max = 1;
        for(int j = 0;j < ch.length;){
            if(map.containsKey(ch[j]) ){
                max = max >= map.size() ? max : map.size();
                for(Map.Entry<Character,Boolean> entry : map.entrySet()){
                    if(entry.getKey() == ch[j]){
                        map.remove(entry.getKey());
                        break;
                    }else{
                        map.remove(entry.getKey());
                    }
                }
            }
            map.put(ch[j],true);
            j++;
        }
        return max >= map.size() ? max : map.size();
    }
}
